// 08.08.[原重复,不可重复选的排列dfs递归]/有重复字符串的排列组合/面试题
// https://leetcode.cn/problems/permutation-ii-lcci
// 解法：字符串副本排序后choice
// 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
// 输入：S = "qqe"
// 输出：[
// "eqq",
// "qeq",
// "qqe"]
// 输入：S = "ab"
// 输出：["ab", "ba"]
// 提示:字符都是英文字母。
// 字符串长度在[1, 9]之间。

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
// ============== 原有重复,不重复选择的排列,排列长度=原字串
class Solution_v1 {
 public:
  vector<string> permutation(string S) {
    sort(S.begin(), S.end());  //排序重复相邻
    vector<int> visitFg(S.size());
    vector<string> res;
    string path;
    dfs_vis(S, path, S.length(), visitFg, res);
    return res;
  }
  // reqNum : 需要的个数
  void dfs_vis(const string& src, string& path, size_t reqNum,
               vector<int>& visitFg, vector<string>& res) {
    if (path.size() == reqNum) {
      res.push_back(path);
      return;
    }
    for (size_t i = 0; i < src.length(); i++) {
      if (visitFg[i]) {
        continue;
      }
      // 有重复字符已经访问，跳过
      if (i > 0 && src[i] == src[i - 1] && visitFg[i - 1]) continue;
      path += src[i];
      visitFg[i] = 1;
      dfs_vis(src, path, reqNum, visitFg, res);
      path.pop_back();  //回溯
      visitFg[i] = 0;
    }
  }
};

class Solution_v2 {
  size_t LEN = 0;
  const static char VISITED = '*';
  void dfs_delchar(string& choice, string& path, vector<string>& answer) {
    if (path.length() == LEN) {
      answer.push_back(path);
      return;
    }
    for (size_t i = 0; i < choice.length(); i++) {
      if (choice[i] == VISITED) {
        continue;
      }
      if (i > 0 && choice[i - 1] == choice[i]) {
        continue;
      }
      path += choice[i];
      choice[i] = VISITED;
      dfs_delchar(choice, path, answer);
      choice[i] = path.back();
      path.pop_back();
    }
  }

 public:
  vector<string> permutation(string S) {
    LEN = S.length();
    vector<string> res;
    string path;
    string choice(S);
    std::sort(choice.begin(), choice.end());
    dfs_delchar(choice, path, res);
    return res;
  }
};

// ============== 原有重复,不重复选择的排列,排列长度=原字串
class Solution {
 public:
  vector<string> permutation(string S) {
    sort(S.begin(), S.end());  //排序重复相邻
    vector<int> visitFg(S.size());
    vector<string> res;
    string path;
    dfs_vis(S, path, S.length(), visitFg, res);
    return res;
  }
  // reqNum : 需要的个数
  void dfs_vis(const string& src, string& path, size_t reqNum,
               vector<int>& visitFg, vector<string>& res) {
    if (path.size() == reqNum) {
      res.push_back(path);
      return;
    }
    for (size_t i = 0; i < src.length(); i++) {
      if (visitFg[i]) {
        continue;
      }
      // 有重复字符已经访问，跳过
      if (i > 0 && src[i] == src[i - 1] && visitFg[i - 1]) continue;
      path += src[i];
      visitFg[i] = 1;
      dfs_vis(src, path, reqNum, visitFg, res);
      path.pop_back();  //回溯
      visitFg[i] = 0;
    }
  }
};

int main() {
  Solution sol;
  vector<string> res = sol.permutation("aabc");
  for (auto sd : res) PF("%s,\n", sd.c_str());
  return 0;
}
